import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/13 9:52
 * @description
 */
public class Solution {
    public static void main(String[] args) {

    }
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        // 保存要跟换的两个节点，pred保存前一个节点
        TreeNode x = null, y = null, pred = null;


        while (!deque.isEmpty() || root != null) {
            while (root != null) {
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            if (pred != null && root.val < pred.val) {
                y = root;
                if (x == null) {
                    x = pred;
                }else {
                    break;
                }
            }
            pred = root;
            root = root.right;
        }
        swap(x, y);
    }
    public void swap(TreeNode x, TreeNode y) {
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
}
